package WeeklyContest.W198;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class W198 {
        public static void main(String[] args) {
            // Solution s = new Solution();
            // int[][] edges ={ {0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
            // String labels = "abaedcd";
            // s.countSubTrees(7, edges, labels);
        }
}

// //5464. 换酒问题
// class Solution {
//     public int numWaterBottles(int numBottles, int numExchange) {
//         int ans = 0;
//         int bLeft = 0;
//         while(numBottles+bLeft>=numExchange){
//             ans+=numBottles;
//             //现在有numBottles个刚喝完的
//             numBottles+=bLeft; //一共这些
//             bLeft=numBottles%numExchange; //剩的空瓶子
//             numBottles/=numExchange; //刚换了这些新的
//         }
//         ans += numBottles; //最后剩的
//         return ans;
//     }
// }


//5465. 子树中标签相同的节点数
// class Solution {
//     int[] ans;
//     boolean[] finished;
//     Map<Integer,List<Integer>> edgeMap;
//     public int[] countSubTrees(int n, int[][] edges, String labels) {
//         ans = new int[n];
//         finished = new boolean[n];
//         edgeMap = new HashMap<>();
//         for (int[] is : edges) {
//             int p0=is[0];
//             int p1=is[1];
//             if(!edgeMap.containsKey(p0)){
//                 edgeMap.put(p0, new ArrayList<>());
//             }
//             edgeMap.get(p0).add(p1);
//             if(!edgeMap.containsKey(p1)){
//                 edgeMap.put(p1, new ArrayList<>());
//             }
//             edgeMap.get(p1).add(p0);
//         }
//         Map<Character,Integer> map=new HashMap<>();
//             search(n, edgeMap, labels, map, 0);
//         return ans;
//     }




//     private void search(int n,Map<Integer,List<Integer>> edgeMap,String labels,Map<Character,Integer> map,int cur){
//         finished[cur]=true;
//         for (int p : edgeMap.get(cur)) {
//             if(finished[p]) continue;
//             Map<Character,Integer> map0 =  new HashMap<>();
//                 search(n, edgeMap, labels, map0, p);
//                 //把子节点的标签map加入副节点中
//                 for (char key: map0.keySet()) {
//                     map.put(key, map.getOrDefault(key, 0)+map0.get(key));
//                 }
//         }
//         char curLabel = labels.charAt(cur);
//         int curNums= map.getOrDefault(curLabel,0);
//         map.put(curLabel,curNums+1);
//         ans[cur]=curNums+1;
//     }
// }